#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param heights: a list of integers
    @return: a integer
    """
    def trapRainWater(self, heights):
        if not heights:
            return 0

        sum = 0

        left_idx = 0
        right_idx = len(heights) - 1

        left_max = heights[left_idx]
        right_max = heights[right_idx]

        while left_idx < right_idx:
            # left_max = max(heights[left_idx], left_max)
            # right_max = max(heights[right_idx], right_max)
            if left_max <= right_max:
                sum += left_max - heights[left_idx]
                left_idx += 1
                left_max = max(heights[left_idx], left_max)
            else:
                sum += right_max - heights[right_idx]
                right_idx -= 1
                right_max = max(heights[right_idx], right_max)

        return sum


def test():
    s = Solution()
    ret = s.trapRainWater( [0,1,0,2,1,0,1,3,2,1,2,1])
    print(ret)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
